package week_05.sort;

import java.util.ArrayList;
import java.util.List;

public class QuickSort implements Sort {
    @Override
    public String toString() {
        return "QuickSort::";
    }

    @Override
    public void sort(int[] nums) {

        quickSort(nums, 0, nums.length - 1);
    }

    private void quickSort(int[] nums, int l, int r) {
        // 选择一个基准进行排序 外部有序 内部无序
        // 大于基准的挪到右边r-- 小于基准的挪到左右l++
        // 当处理完最后一个大于基准的数据和基准做一个交换
        // 分为 小于 等于 大于基准三个区
        if (l >= r) return;
        int privot = partition(nums, l, r);
        quickSort(nums, l, privot);
        quickSort(nums, privot + 1, r);
    }

    public int partition(int[] nums, int l, int r) {
        int privot = l + (int) ((r - l + 1) * Math.random());
        System.out.println("1:l:" + l + ":r:" + r + ":privot:" + privot);

        int privotVal = nums[privot];

        while (l <= r) {
            // 找到左边下一个需要交换的大的数
            while (nums[l] < privotVal) l++;
            // 找到右边下一个需要交换的小的数
            while (nums[r] > privotVal) r--;
            if (l <= r) {
                swap(nums, l, r);
                l++;
                r--;
            }
        }
        System.out.println("2:l:" + l + ":r:" + r + ":privot:" + privot);
        return r;
    }


    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;

    }
}
